﻿//#define _CRT_SECURE_NO_WARNINGS 1
//
//
//
//
//
////double Division(int a, int b)
////{
////    // 当b == 0时抛出异常
////    if (b == 0)
////        throw "Division by zero condition!";
////    else
////        return ((double)a / (double)b);
////}
////
////int AccessEle(int n)
////{
////    int arr[10] = { 0 };
////    if (n >= 10)
////        throw -1;
////    else
//////        return arr[n];
////}
////void Func()
////{
////    cout << Division(10, 1) << endl;
////    cout << AccessEle(11) << endl;
////}
//
//
////int main()
////{
////    try {
////        Func();
////    }
////    catch (const char* errmsg)
////    {
////        cout << errmsg << endl;
////    }
////    catch (int i)
////    {
////        cout << i << endl;
////    }
////    return 0;
////}
//
//
////int func1(int a)
////{
////    if (a % 2 == 0)
////    {
////        string s("a为偶数!");
////        throw s;//识别成右值，将亡值
////        // 移动构造，效率高
////    }
////}
////
////void Func()
////{
////    func1(0);
////}
////int main()
////{
////    try {
////        Func();
////    }
////    catch (const string& errmsg)
////        // 这里的errmsg捕或的对象是s嘛？
////        // 不是，s是一个局部变量，出了作用域调用析构函数就被消耗
////        // 这是抛出的是s对象的拷贝,这里捕获的是临时对象
////        // 临时对象会被catch以后被销毁
////    {
////        cout << errmsg << endl;
////    }
////}
//
////#include <Windows.h>
////
////// 服务器开发中通常使用的异常继承体系
////class Exception
////{
////public:
////	Exception(const string& errmsg, int id)
////		:_errmsg(errmsg)
////		, _id(id)
////	{}
////
////	virtual string what() const
////	{
////		return _errmsg;
////	}
////
////protected:
////	string _errmsg;  // 错误描述
////	int _id;         // 错误编号
////};
////
////// 继承和多态
////class SqlException : public Exception
////{
////public:
////	SqlException(const string& errmsg, int id, const string& sql)
////		:Exception(errmsg, id)
////		, _sql(sql)
////	{}
////
////	virtual string what() const
////	{
////		string str = "SqlException:";
////		str += _errmsg;
////		str += "->";
////		str += _sql;
////		return str;
////	}
////private:
////	const string _sql;
////};
////
////class CacheException : public Exception
////{
////public:
////	CacheException(const string& errmsg, int id)
////		:Exception(errmsg, id)
////	{}
////
////	virtual string what() const
////	{
////		string str = "CacheException:";
////		str += _errmsg;
////		return str;
////	}
////};
////
////class HttpServerException : public Exception
////{
////public:
////	HttpServerException(const string& errmsg, int id, const string& type)
////		:Exception(errmsg, id)
////		, _type(type)
////	{}
////
////	virtual string what() const
////	{
////		string str = "HttpServerException:";
////		str += _type;
////		str += ":";
////		str += _errmsg;
////		return str;
////	}
////private:
////	const string _type;
////};
////
////void SQLMgr()
////{
////	srand(time(0));
////	if (rand() % 7 == 0)
////	{
////		throw SqlException("权限不足", 100, "select * from name = '张三'");
////	}
////
////	cout << "!!!!!!!!!!!!!!!!!!!!!!!!运行成功" << endl;
////}
////
////void CacheMgr()
////{
////	srand(time(0));
////	if (rand() % 5 == 0)
////	{
////		throw CacheException("权限不足", 100);
////	}
////	else if (rand() % 6 == 0)
////	{
////		throw CacheException("数据不存在", 101);
////	}
////	SQLMgr();
////}
////
////void HttpServer()
////{
////	srand(time(0));
////	if (rand() % 3 == 0)
////	{
////		throw HttpServerException("请求资源不存在", 100, "get");
////	}
////	else if (rand() % 4 == 0)
////	{
////		throw HttpServerException("权限不足", 101, "post");
////	}
////
////	CacheMgr();
////}
////
//////int main()
//////{
//////	srand(time(0));
//////	while (1)
//////	{
//////		Sleep(1000);
//////
//////		try {
//////			HttpServer(); // io
//////		}
//////		catch (const Exception& e) // 这里捕获父类对象就可以
//////		{
//////			// 多态
//////			cout << e.what() << endl;
//////		}
//////		catch (...)
//////		{
//////			cout << "Unkown Exception" << endl;
//////		}
//////	}
//////	return 0;
//////}
////
//
////double Division(int a, int b)
////{
////    // 当b == 0时抛出异常
////    if (b == 0)
////        throw "Division by zero condition!";
////    else
////        return ((double)a / (double)b);
////}
////
////class A
////{
////public:
////	A()
////	{ 
////		cout << "A()" << endl;
////		_ptr1 = new int;//抛异常
////		Division(10, 0);
////		_ptr2 = new int;//此时ptr2没有初始化
////	}
////
////	~A()
////	{
////		cout << "~A()" << endl;
////		delete _ptr1;
////		delete _ptr2;//ptr2没有初始化，会delete掉野指针
////		//析构掉野指针导致程序出现错误
////		//但是我们的编译器把_ptr2初始化为空指针了
////		//delete掉空指针是不会报错
////	}
////private:
////	int* _ptr1;
////	int* _ptr2;
////};
////int main()
////{
////	try
////	{
////		A aa;
////	}
////	catch (...)
////	{
////		cout << "Unkown Exception" << endl;
////	}
////}
//
//
//
////double Division(int a, int b)
////{
////	 当b == 0时抛出异常
////	if (b == 0)
////	{
////		throw "Division by zero condition!";
////	}
////	return (double)a / (double)b;
////}
////void Func()
////{
////	 这里可以看到如果发生除0错误抛出异常，另外下面的array没有得到释放。
////	int* array = new int[10];
////	int len, time;
////	cin >> len >> time;
////	cout << Division(len, time) << endl;
////
////	cout << "delete []" << array << endl;
////	delete[] array;
////}
////int main()
////{
////	try
////	{
////		Func();
////	}
////	catch (const char* errmsg)
////	{
////		cout << errmsg << endl;
////	}
////	return 0;
////}
//
//double Division(int a, int b)
//{
//	// 当b == 0时抛出异常
//	if (b == 0)
//	{
//		throw "Division by zero condition!";
//	}
//	return (double)a / (double)b;
//}
////void Func()
////{
////	// 这里可以看到如果发生除0错误抛出异常，另外下面的array没有得到释放。
////	// 所以这里捕获异常后并不处理异常，异常还是交给外面处理，这里捕获了再
////	// 重新抛出去。
////	int* array = new int[10];
////	try {
////		int len, time;
////		cin >> len >> time;
////		cout << Division(len, time) << endl;
////	}
////	catch (...)
////	{
////		// 捕获异常不是为了处理异常
////		// 是为了释放内存，然后异常再重新抛出
////		cout << "delete []" << array << endl;
////		delete[] array;
////		throw;
////	}
////	// ...
////	cout << "delete []" << array << endl;
////	delete[] array;
////}
////int main()
////{
////	try
////	{
////		Func();
////	}
////	catch (const char* errmsg)
////	{
////		cout << errmsg << endl;
////	}
////	return 0;
////}
////
////double Division(int a, int b) throw(const char*)
////{
////	// 当b == 0时抛出异常
////	if (b == 0)
////	{
////		throw "Division by zero condition!";
////	}
////	return (double)a / (double)b;
////}
////
////void fyy() throw()
////{
////	int len, time;
////	cin >> len >> time;
////	cout << Division(len, time) << endl;
////}
////
////// 下面程序及其难看
////// 智能指针解决
////void fxx()
////{
////	int* p1 = new int[10];
////	int* p2, *p3;
////	try
////	{
////		p2 = new int[20];
////		try {
////			p3 = new int[30];
////		}
////		catch (...)
////		{
////			delete[] p1;
////			delete[] p2;
////			throw;
////		}
////	}
////	catch (...)
////	{
////		delete[] p1;
////		throw;
////	}
////
////	//...
////
////	delete[] p1;
////	delete[] p2;
////	delete[] p3;
////}
////
////
////class SmartPtr
////{
////public:
////	SmartPtr(int* ptr)
////		:_ptr(ptr)
////	{}
////
////	~SmartPtr()
////	{
////		cout << "delete[] _ptr" << endl;
////
////		delete[] _ptr;
////	}
////
////	// operator*
////	// operator->
////	// operator[]
////
////private:
////	int* _ptr;
////};
////
////void fxx()
////{
////	SmartPtr sp1(new int[10]);
////	SmartPtr sp2(new int[10]);
////	SmartPtr sp3(new int[10]);
////
////	int x, y;
////	cin >> x >> y;
////	Division(x, y);
////}
////
////int main()
////{
////	try
////	{
////		fxx();
////	}
////	catch (const char* errmsg)
////	{
////		cout << errmsg << endl;
////	}
////
////	return 0;
////}
//
////class Solution
////{
////public:
////	vector<int> sortArray(vector<int>& nums)
////	{
////		srand(time(NULL)); // 种下?个随机数种?
////		qsort(nums, 0, nums.size() - 1);
////		return nums;
////	}
////	// 快排
////	void qsort(vector<int>& nums, int l, int r)
////	{
////		if (l >= r) return;
////		// 数组分三块
////		int key = getRandom(nums, l, r);
////		int i = l, left = l - 1, right = r + 1;
////		while (i < right)
////		{
////			if (nums[i] < key) swap(nums[++left], nums[i++]);
////			else if (nums[i] == key) i++;
////			else swap(nums[--right], nums[i]);
////		}
////		// [l, left] [left + 1, right - 1] [right, r]
////		qsort(nums, l, left);
////		qsort(nums, right, r);
////	}
////	int getRandom(vector<int>& nums, int left, int right)
////	{
////		int r = rand();
////		return nums[r % (right - left + 1) + left];
////	}
////};
//
//
////class Solution
////{
////	vector<int> tmp;
////public:
////	vector<int> sortArray(vector<int>& nums)
////	{
////		tmp.resize(nums.size());
////		mergeSort(nums, 0, nums.size() - 1);
////		return nums;
////	}
////	void mergeSort(vector<int>& nums, int left, int right)
////	{
////		if (left >= right) return;
////		// 1. 选择中间点划分区间
////		int mid = (left + right) >> 1;
////		// [left, mid] [mid + 1, right]
////		// 2. 把左右区间排序
////		mergeSort(nums, left, mid);
////		mergeSort(nums, mid + 1, right);
////		// 3. 合并两个有序数组
////		int cur1 = left, cur2 = mid + 1, i = 0;
////		while (cur1 <= mid && cur2 <= right)
////			tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
////			// 处理没有遍历完的数组
////			while (cur1 <= mid) tmp[i++] = nums[cur1++];
////		while (cur2 <= right) tmp[i++] = nums[cur2++];
////		// 4. 还原
////		for (int i = left; i <= right; i++)
////			nums[i] = tmp[i - left];
////	}
////};
//
////class Solution
////{
////	vector<int> ret;
////	vector<int> index; // 记录 nums 中当前元素的原始下标
////	int tmpNums[500010];
////	int tmpIndex[500010];
////public:
////	vector<int> countSmaller(vector<int>& nums)
////	{
////		int n = nums.size();
////		ret.resize(n);
////		index.resize(n);
////		// 初始化?下 index 数组
////		for (int i = 0; i < n; i++)
////			index[i] = i;
////		mergeSort(nums, 0, n - 1);
////		return ret;
////	}
////
////	void mergeSort(vector<int>& nums, int left, int right)
////	{
////		if (left >= right) return;
////		// 1. 根据中间元素，划分区间
////		int mid = (left + right) >> 1;
////		// [left, mid] [mid + 1, right]
////		// 2. 先处理左右两部分
////		mergeSort(nums, left, mid);
////		mergeSort(nums, mid + 1, right);
////		// 3. 处理?左?右的情况
////		int cur1 = left, cur2 = mid + 1, i = 0;
////		while (cur1 <= mid && cur2 <= right) // 降序
////		{
////			if (nums[cur1] <= nums[cur2])
////			{
////				tmpNums[i] = nums[cur2];
////				tmpIndex[i++] = index[cur2++];
////			}
////			else
////			{
////				ret[index[cur1]] += right - cur2 + 1; // 重点
////				tmpNums[i] = nums[cur1];
////				tmpIndex[i++] = index[cur1++];
////			}
////		}
////		// 4. 处理剩下的排序过程
////		while (cur1 <= mid)
////		{
////			tmpNums[i] = nums[cur1];
////			tmpIndex[i++] = index[cur1++];
////		}
////		while (cur2 <= right)
////		{
////			tmpNums[i] = nums[cur2];
////			tmpIndex[i++] = index[cur2++];
////		}
////		for (int j = left; j <= right; j++)
////		{
////			nums[j] = tmpNums[j - left];
////			index[j] = tmpIndex[j - left];
////		}
////	}
////};
//
////class Solution
////{
////	int tmp[50010];
////public:
////	int reversePairs(vector<int>& nums)
////	{
////		return mergeSort(nums, 0, nums.size() - 1);
////	}
////	int mergeSort(vector<int>& nums, int left, int right)
////	{
////		if (left >= right) return 0;
////		int ret = 0;
////		// 1. 先根据中间元素划分区间
////		int mid = (left + right) >> 1;
////		// [left, mid] [mid + 1, right]
////		// 2. 先计算左右两侧的翻转对
////		ret += mergeSort(nums, left, mid);
////		ret += mergeSort(nums, mid + 1, right);
////		// 3. 先计算翻转对的数量
////		int cur1 = left, cur2 = mid + 1, i = left;
////		while (cur1 <= mid) // 降序的情况
////		{
////			while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
////			if (cur2 > right)
////				break;
////			ret += right - cur2 + 1;
////			cur1++;
////		}
////		// 4. 合并两个有序数组
////		cur1 = left, cur2 = mid + 1;
////		while (cur1 <= mid && cur2 <= right)
////			tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
////		while (cur1 <= mid) tmp[i++] = nums[cur1++];
////		while (cur2 <= right) tmp[i++] = nums[cur2++];
////		for (int j = left; j <= right; j++)
////			nums[j] = tmp[j];
////
////		return ret;
////	}
////};
//
////class Solution
////{
////public:
////	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
////	{
////		ListNode* cur1 = l1, * cur2 = l2;
////		ListNode* newhead = new ListNode(0); // 创建?个虚拟头结点，记录最终结果
////		ListNode* tail = newhead; // 尾指针
////		int t = 0; // 记录进位
////		while (cur1 || cur2 || t)
////		{
////			// 先加上第?个链表
////			if (cur1)
////			{
////				t += cur1->val;
////				cur1 = cur1->next;
////			}
////			// 加上第?个链表
////			if (cur2)
////			{
////				t += cur2->val;
////				cur2 = cur2->next;
////			}
////			tail->next = new ListNode(t % 10);
////			tail = tail->next;
////			t /= 10;
////		}
////
////		ListNode* head = newhead->next;
////		delete newhead;
////		return head;
////	}
////};
//
////class Solution
////{
////public:
////	void reorderList(ListNode* head)
////	{
////		// 处理边界情况
////		if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return head;
////			// 1. 找到链表的中间节点 - 快慢双指针（?定要画图考虑 slow 的落点在哪?）
////			ListNode * slow = head, *fast = head;
////			while (fast && fast->next)
////			{
////				slow = slow->next;
////					fast = fast->next->next;
////			}
////		// 2. 把 slow 后?的部分给逆序 - 头插法
////		ListNode* head2 = new ListNode(0);
////			ListNode* cur = slow->next;
////			slow->next = nullptr; // 注意把两个链表给断开
////		while (cur)
////		{
////			ListNode* next = cur->next;
////			cur->next = head2->next;
////			head2->next = cur;
////			cur = next;
////		}
////		// 3. 合并两个链表 - 双指针
////		ListNode* ret = new ListNode(0);
////		ListNode* prev = ret;
////		ListNode* cur1 = head, * cur2 = head2->next;
////		while (cur1)
////		{
////			// 先放第?个链表
////			prev->next = cur1;
////			cur1 = cur1->next;
////			prev = prev->next;
////			// 再放第?个链表
////			if (cur2)
////			{
////				prev->next = cur2;
////				prev = prev->next;
////				cur2 = cur2->next;
////			}
////		}
////		delete head2;
////		delete ret;
////	}
////};
//
////class Solution
////{
////	struct cmp
////	{
////		bool operator()(const ListNode* l1, const ListNode* l2)
////		{
////			return l1->val > l2->val;
////		}
////	};
////public:
////	ListNode* mergeKLists(vector<ListNode*>& lists)
////	{
////		// 创建?个?根堆
////		priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
////		// 让所有的头结点进??根堆
////		for (auto l : lists)
////			if (l) heap.push(l);
////
////		// 合并 k 个有序链表
////		ListNode* ret = new ListNode(0);
////		ListNode* prev = ret;
////		while (!heap.empty())
////		{
////			ListNode* t = heap.top();
////			heap.pop();
////			prev->next = t;
////			prev = t;
////			if (t->next) heap.push(t->next);
////		}
////		prev = ret->next;
////		delete ret;
////		return prev;
////	}
////};
//
////class Solution
////{
////public:
////	ListNode* mergeKLists(vector<ListNode*>& lists)
////	{
////		return merge(lists, 0, lists.size() - 1);
////	}
////	ListNode* merge(vector<ListNode*>& lists, int left, int right)
////	{
////		if (left > right) return nullptr;
////		if (left == right) return lists[left];
////		// 1. 平分数组
////		int mid = left + right >> 1;
////		// [left, mid] [mid + 1, right]
////		// 2. 递归处理左右区间
////		ListNode* l1 = merge(lists, left, mid);
////		ListNode* l2 = merge(lists, mid + 1, right);
////		// 3. 合并两个有序链表
////		return mergeTowList(l1, l2);
////	}
////	ListNode* mergeTowList(ListNode* l1, ListNode* l2)
////	{
////		if (l1 == nullptr) return l2;
////		if (l2 == nullptr) return l1;
////		// 合并两个有序链表
////		ListNode head;
////		ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
////		head.next = nullptr;
////		while (cur1 && cur2)
////		{
////			if (cur1->val <= cur2->val)
////			{
////				prev = prev->next = cur1;
////				cur1 = cur1->next;
////			}
////			else
////			{
////				prev = prev->next = cur2;
////				cur2 = cur2->next;
////			}
////		}
////		if (cur1) prev->next = cur1;
////		if (cur2) prev->next = cur2;
////		return head.next;
////	}
////};
//
////#include <vector>
////#include <unordered_map>
////#include <iostream>
////#
////using namespace std;
////
////class Solution
////{
////public:
////	string longestPalindrome(string s)
////	{
////		// 中⼼扩展算法
////		int begin = 0, len = 0, n = s.size();
////		for (int i = 0; i < n; i++) // 依次枚举所有的中点
////		{
////			// 先做⼀次奇数⻓度的扩展
////			int left = i, right = i;
////			while (left >= 0 && right < n && s[left] == s[right])
////			{
////				left--;
////				right++;
////			}
////			if (right - left - 1 > len)
////			{
////				begin = left + 1;
////				len = right - left - 1;
////			}
////			// 偶数长度的扩展
////			left = i, right = i + 1;
////			while (left >= 0 && right < n && s[left] == s[right])
////			{
////				left--;
////				right++;
////			}
////			if (right - left - 1 > len)
////			{
////				begin = left + 1;
////				len = right - left - 1;
////			}
////		}
////		return s.substr(begin, len);
////	}
////};
//
//
//
//
//
//
//
//
//
//
//
//
//
//
